#!/usr/bin/env python 
# -*- coding: utf-8 -*-
# @Time    : 2022/9/21 20:03
# @Author  : Junzhao
# @File    : marge.py
# @Software: PyCharm


def merge(a_list: list, left, center, right):
    temp_list = []
    i = left
    temp_left = left
    mid = center + 1
    while left <= center and right >= mid:
        if a_list[left] <= a_list[mid]:
            temp_list[temp_left] = a_list[left]
            temp_left += 1
            left += 1
        else:
            temp_list[temp_left] = a_list[mid]
            temp_left += 1
            mid += 1
    while mid <= right:
        temp_list[temp_left] = a_list[mid]
        temp_left += 1
        mid += 1
    while left <= center:
        temp_list[temp_left] = a_list[left]
        temp_left += 1
        left += 1
    # 赋值
    while i <= right:
        a_list[i] = temp_list[i]
        i += 1
    pass


def sort(a_list: list, left, right):
    if left < right:
        # 分
        center = (left + right) / 2
        sort(a_list, left, center)
        sort(a_list, center + 1, right)
        # 治
        merge(a_list, left, center, right)
    pass


if __name__ == '__main__':
    test_list = [1, 3, 34, 56, 73, 45]
    print(test_list)
    sort(test_list, 0, len(test_list) - 1)
    print(test_list)

